﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution236
{
    //先暴力一下，遍历树，分别判断每个节点，是不是这两个节点的父亲,狗屎代码

    int min = int.MaxValue;
    TreeNode res;
    public TreeNode LowestCommonAncestor2(TreeNode root, TreeNode p, TreeNode q)
    {
        res=new TreeNode();

        DFS(root,p,q);


        return root;
    }

    private void DFS(TreeNode root, TreeNode p, TreeNode q)
    {//判断

        if(root == null) return;    
      int depth=  CheckParent(root,p,q);
        if(depth != -1) { 
           //更新最小深度
           if(depth < min) {

                res=root;
                min = depth;
            }
        }


        DFS(root.left,p,q);
        DFS(root.right,p,q);
       


    }
    private int CheckParent(TreeNode root, TreeNode p, TreeNode q)
    {//判断root是不是pq的祖先


      int pHaveP = Check(root, p,0);
      int qHaveP = Check(root, q,0);
        Console.WriteLine(pHaveP);
        Console.WriteLine(qHaveP);

        //返回最小深度
        if (pHaveP ==-1&& qHaveP == -1) {//不是孩子

            return -1;
        }
        else if(pHaveP ==-1)
        {
            return qHaveP;
        }
        else if (qHaveP == -1)
        {
            return pHaveP;
        }
        else
        {
            return Math.Min(pHaveP,qHaveP);
        }



    }
    private int Check(TreeNode root, TreeNode cur, int depth)
    {//判断

        if (root == cur)
        {

            return depth;

        }
        if(root==null)
        {

            return -1;//不是祖先
        }

       
        

        Console.WriteLine("这句话会执行吗");
        return Math.Max(Check(root.left, cur, depth + 1), Check(root.right, cur, depth + 1));

    }

    TreeNode res1 = new TreeNode();
    //判断条件
    public TreeNode LowestCommonAncestor4(TreeNode root, TreeNode p, TreeNode q)
    {
        res1 = new TreeNode();

       MyDFS(root, p, q);


        return res1;
    }

    private bool MyDFS(TreeNode root, TreeNode p, TreeNode q)
    {
        //左右根的顺序

        if(root == null)
        {
            return false;//肯定不包含
        }

      bool lson=  MyDFS(root.left, p, q);
        bool rson = MyDFS(root.right, p, q);

        //判断自己左孩子包含p或者q
        //lson如果pq都有，rson肯定是false，所以不是最近的祖先
        //根节点是p或者q，那么两个孩子只能有剩下的那个
        if (lson && rson || ((root == p || root == q)&&(lson||rson)))
        {

            res1=root; 

        }


//左孩子有或者右孩子有，都说明自己有pq
return (lson||rson)||(root==p|| root == q);
    }
    public TreeNode LowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q)
    {
        if (root == null || root == p || root == q) return root;
        TreeNode left = LowestCommonAncestor(root.left, p, q);//去左子树找最近公共祖先
        TreeNode right = LowestCommonAncestor(root.right, p, q);//去右子树找最近公共祖先
        if (left == null) return right;
        if (right == null) return left;
        return root;
    }
    //使用哈希表记录父亲节点
    public TreeNode LowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q)
    {

        TreeNode res = null;
      Dictionary<int, TreeNode> parent = new Dictionary<int, TreeNode>();
     
        HashSet<int> pParent = new HashSet<int>();//存的是同一个节点
        

        GetParent(root, parent);
       

        while(p != null)
        {
            pParent.Add(p.val);
            if (parent.ContainsKey(p.val))
            {
               
                Console.WriteLine("P" + p.val);
                p = parent[p.val];//p找到自己的所有祖父节点
            }
            else
            {
                p = null;
            }
           

        }



        while (q!= null)
        {
            Console.WriteLine(q.val);
            if (pParent.Contains(q.val))
                {
                Console.WriteLine("找到");

                return q;
                }

            if (parent.ContainsKey(q.val))
            {
                q = parent[q.val];//q找到自己的当前祖父节点
            }
            else
            {
                q = null;
            }
    


        }

        Console.WriteLine(res);
        return null;


    }

    //存父亲
    private void GetParent(TreeNode root, Dictionary<int, TreeNode> parent)
    {

        if (root.left != null)
        {
            parent[root.left.val] = root;
            GetParent(root.left, parent);
          
        }
        if (root.right != null)
        {
            parent[root.right.val] = root;


            GetParent(root.right, parent);

        }
      
    }
}

class Program236
{
    static void Main236(string[] args)
    {

        



        //构造二叉树
        int[] preorder = [3,5,6,2,7,4,1,0,8];
        int[] inorder = [6,5,7,2,4,3,0,1,8];
        Solution105 solBuildTree = new Solution105();
        TreeNode root = solBuildTree.BuildTree(preorder, inorder);

        Solution102 LevelOrder = new Solution102();
        IList<IList<int>> res = LevelOrder.LevelOrder(root);
        for (int i = 0; i < res.Count; i++)
        {
            for (int j = 0; j < res[i].Count; j++)
            {


                //Console.Write(res[i][j] + ",");
            }
            Console.WriteLine();
        }




        //
        Solution236 solution = new Solution236();

      TreeNode result=  solution.LowestCommonAncestor(root, root.left,root.right);
        Console.WriteLine(result.val);
    }
}